/*
7.26
time:20201209 12:11 PM
key:1.
user：ldc
*/

#include <iostream>
using namespace std;
#include<stack>
#include<queue>
class Tree
{
public:
	int data;
	Tree* lchild;
	Tree* rchild;
	bool left_flag = false;   //左指针域类型  false：指向子节点、true：前驱或后继线索
	bool right_flag = false;  //右指针域类型  false：指向子节点、true：前驱或后继线索

	Tree()
	{
		data = -1;
		lchild = NULL;
		rchild = NULL;
	}
};
//写入树
void write(Tree* node)
{
	if (node != NULL)
	{
		int a;
		cin >> a;
		if (a != 0)
		{
			node->data = a;
			node->lchild = new Tree;
			node->rchild = new Tree;
		}
		write(node->lchild);
		write(node->rchild);
	}
}
//先序遍历改造树(空节点改为NULL)
void change(Tree* node)
{
	if (node != NULL)

	{
		if (node->lchild->data == -1)
		{
			node->lchild = NULL;
		}
		if (node->rchild->data == -1)
		{
			node->rchild = NULL;
		}
		change(node->lchild);
		change(node->rchild);

	}
}
//中序遍历输出树()
void PerOrder_read(Tree* node, queue<int>&sort)
{
	if (node != NULL)

	{
		PerOrder_read(node->lchild, sort);
		cout << node->data << " ";
		sort.push(node->data);
		PerOrder_read(node->rchild, sort);

	}
}



int main()
{
	Tree* head = new Tree;
	queue<int>sort;
	

	//使用一下输入
	//1 2 3 0 0 4 0 5 0 0 6 0 7 0 8 0 0
	//5 3 2 1 0 0 0 4 0 0 7 6 0 0 8 0 9 0 0
	write(head);
	cout << "\n先序遍历改造树(0空节点改为NULL)" << endl;
	change(head);
	cout << "\n中序遍历输出树" << endl;
	PerOrder_read(head,sort);
	cout << "\n通过中序遍历结果检查是否是递增顺序" << endl;
	int x;
	x = sort.front();
	sort.pop();
	while(!sort.empty())
	{
	
	if (x > sort.front())
	{
		cout << "不是二叉搜索树";
		break;
	}
	x = sort.front();
	sort.pop();
	}
	

}




